1. Field of the Invention
The present invention relates to reading two-dimensional symbologies, and, in particular, to a method and apparatus for locating two-dimensional symbols in pixel images.
2. Statement of Related Art
U.S. Pat. Nos. 4,874,936 (Chandler et al.) and 4,896,029 (Chandler et al.) disclose articles, processes, and systems for polygonal information encoding, whereby information is encoded in a two-dimensional symbol comprising a plurality of polygons and an acquisition target. The purpose of an acquisition target is to have a known and easily recognized pattern which provides finding information for locating the symbol in the field of view of a sensing device.
One acquisition target disclosed in the '936 and '029 patents is of a geometric shape having optical properties capable of generating an easily recognizable video signal when scanned with an optical sensor across a linear scan line passing through the geometric center of the acquisition target. For example, the acquisition target may be a plurality of concentric rings of contrasting reflectivity (e.g., the bull's-eye pattern of FIG. 3), which will yield a periodic video signal when scanned linearly through its center.
The '936 and '029 patents disclose analog and digital methods for locating an acquisition target comprising a plurality of concentric rings. According to these methods, encoded labels are passed through a predetermined illuminated area and optically scanned by means of an electronically operated optical sensor. Alternatively, a hand-held optical scanner may be passed over the labels. In either case, the optical sensor produces an output which is an analog electrical signal corresponding to the intensities of the individual reflective properties of each area of a label, as recorded by the individual pixels of the optical sensor.
According to an analog method for locating the acquisition target, the analog signal generated by the optical sensor is filtered using an analog bandpass filter. The filter output is then compared to a signal corresponding to a line passing through the center of an ideal acquisition target. The center of the acquisition target is located when the output of the analog bandpass filter most closely approximates the ideal acquisition target signal. The analog signal is simultaneously digitized on a continuous basis by means of an analog-to-digital converter and stored in an image buffer. After locating the acquisition target, the stored digitized data representing the entire label is available for further decode processing.
According to a digital method for locating the acquisition target, the stored digital data representing the entire label is first filtered using a one-dimensional digital bandpass filter corresponding to a line through the center of an ideal acquisition target. This one-dimensional digital filter is used to find the coarse location of the acquisition target. After the coarse location is found, one or two two-dimensional digital filters may be used to find the fine location of the acquisition target.
Both the analog and digital methods disclosed in the '936 and '029 patents require the ideal acquisition target be of the same size as the imaged acquisition target. The location of the imaged acquisition target is determined by finding the region in the image that most closely matches the ideal acquisition target.
The two-dimensional filters are more accurate than the one-dimensional filter, but are slower because they require more computations. The one-dimensional filter is faster, but is less accurate and can result in false positive locations of the acquisition target. That is, the one-dimensional filter may falsely indicate that a particular location in the pixel image corresponds to the acquisition target, when it does not. This may occur where the size of the data-encoding elements (e.g., hexagons) in the two-dimensional symbol is of the same order of magnitude as the thickness of the concentric rings of the acquisition target. The two-dimensional filters are used after the coarse one-dimensional filter for two purposes: (1) to reject the false positive locations from the one-dimensional filter and (2) to find the fine location of the acquisition target for true positive locations.